class Solution
{
public:
    int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>> &composition, vector<int> &stock, vector<int> &cost)
    {
        int result = 0;
        for (int i = 0; i < k; ++i)
        {
            result = max(result, maxAlloysOfMachine(budget, composition[i], stock, cost));
        }
        return result;
    }

    int maxAlloysOfMachine(int budget, vector<int> &consume, vector<int> &stock, vector<int> &cost)
    {
        int n = consume.size();
        auto checkAnswer = [&](long long x)
        {
            long long totalExtraCost = 0;
            for (int i = 0; i < n; ++i)
            {
                long long extra = max(0ll, x * consume[i] - stock[i]);
                totalExtraCost += extra * cost[i];
            }
            return totalExtraCost <= budget;
        };

        int left = 0, right = 1e9;
        while (left < right)
        {
            int mid = (left + right + 1) / 2;
            if (checkAnswer(mid))
            {
                left = mid;
            }
            else
            {
                right = mid - 1;
            }
        }
        return left;
    }
};